package leetcode_100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class M20 {

	public static void main(String[] args) {
		/*int [] nums1= {1,1,2,2,3,4,5,5};
		removeDuplicates(nums1);*/
		//System.out.println(divide(9, 4));
		String s="barfoothefoobarman";
		String strs[]= {"foo","bar"};
/*		List<Integer> res=findSubstring(s, strs);
		System.out.println(res.size());*/
		Map<Integer,List<Integer>> map=findSubstringHelp(s, strs);

	}
	public static int removeDuplicates(int[] nums) {
		//{1,1,2,2,3,4,5,5}
		  int i = 0;//i也是遍历指针
		    for (int n : nums)
		        if (i == 0 || n > nums[i-1])//除了第一个数 其他数均检查是否比i指针的数大 如果有 i++ 否则不变 
		        	//i不仅保存不重复的个数  还停留在目前最大的坐标位置的前一个 
 		            nums[i++] = n;
		    return i;
	}
	
	public static int strStr(String haystack, String needle) {
		if(needle.length()==0)
			return 0;
		if(haystack.length()<needle.length())
			return -1;
		for(int i=0;i<=haystack.length()-needle.length();++i) {
			if(haystack.substring(i, i+1).equals(needle.substring(0, 1))){
				int j=1;
				while(j<needle.length()){
					if(haystack.substring(i+j, i+j+1).equals(needle.substring(j,j+1))){
						++j;
					}
					else
						break;
				}
				if(j==needle.length())
					return i;
			}
		}
        return -1;
    }
	
	public static int divide(int dividend, int divisor) {
		long result = divideLong(dividend, divisor);
		return result > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)result;
	}

	// It's easy to handle edge cases when
	// operate with long numbers rather than int
	public static long divideLong(long dividend, long divisor) {
		
		// Remember the sign
		boolean negative = dividend < 0 != divisor < 0;
		
		// Make dividend and divisor unsign
		if (dividend < 0) dividend = -dividend;
		if (divisor < 0) divisor = -divisor;
		
		// Return if nothing to divide
		if (dividend < divisor) return 0;
		
		// Sum divisor 2, 4, 8, 16, 32 .... times
	    long sum = divisor;
	    long divide = 1;
	    while ((sum+sum) <= dividend) {
	    	sum += sum;
	    	divide += divide;
	    }
	    
	    // Make a recursive call for (devided-sum) and add it to the result
	    return negative ? -(divide + divideLong((dividend-sum), divisor)) :
	    	(divide + divideLong((dividend-sum), divisor));
	}

	public static List<Integer> findSubstring(String s, String[] words) {
		List<Integer>  res=new ArrayList<Integer>();
		int length=words[0].length();//待查数组中字符串的长度
		int nums=words.length;//待查数组目前待查的个数
		int i=0;
        while(i<=s.length()-length) {
        	int j=0;
        	while(j<nums) {//开始在数组中找
        		//System.out.println(s.substring(i, i+length));
        		if(words[j].equals(s.substring(i, i+length))) {//找到一个
        			res.add(i);
        			if(res.size()==words.length)
        				return res;
        			words[j]=words[nums-1];
        			--nums;
        			continue;//终止当前操作 重新开始找
        		};
        		++j;
        	}
        	++i;
        }
        return res;
    }
	
	public static Map<Integer,List<Integer>> findSubstringHelp(String s, String[] words){
		Map<Integer,List<Integer>> res= new HashMap<Integer,List<Integer>>();
		int length=words[0].length();
		int i=0;
		while(i<=s.length()-length){
			for(int j=0;j<words.length;++j) {
				if(words[j].equals(s.substring(i, i+length))) {//找到
					if(res.containsKey(j)) {
						List<Integer> list=res.get(j);
						list.add(i);//在s中i处找到了子串j
						res.put(j, list);
					}
					else {
						List<Integer> list=new ArrayList<Integer>();
						list.add(i);
						res.put(j, list);
						}
				}
			}
			++i;
		}
		return res;
	}
	

}
